CODE 20. Path Sum II

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/09/19/2013-09-19-CODE 20 Path Sum II/

访问原文「CODE 20. Path Sum II」

public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
	// Start typing your Java solution below
	// DO NOT write main() function
	ArrayList<ArrayList<Integer>> paths = new ArrayList<ArrayList<Integer>>();
	if (null == root) {
		return paths;
	}
	dfs(paths, new ArrayList<Integer>(), root, 0, sum);
	return paths;
}

private void dfs(ArrayList<ArrayList<Integer>> paths,
		ArrayList<Integer> path, TreeNode root, int current, int sum) {
	if (root.left == null && root.right == null) {
		if (current + root.val == sum) {
			path.add(root.val);
			ArrayList<Integer> pathCopy = new ArrayList<Integer>();
			pathCopy.addAll(path);
			paths.add(pathCopy);
			path.remove(path.size() - 1);
		}
	}
	path.add(root.val);
	current += root.val;
	if (root.left != null) {
		dfs(paths, path, root.left, current, sum);
	}
	if (root.right != null) {
		dfs(paths, path, root.right, current, sum);
	}
	path.remove(path.size() - 1);
}

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.
For example:
Given the below binary tree and sum = 22, 5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1

return

[
   [5,4,11,2],
   [5,8,4,5]
]